package algorithm.t202111;

import java.util.*;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/11/28 11:47
 * @description :5道
 * 状态逐渐恢复。今天也是我21岁的最后一天，现在时间是2021-11-28 21:16:07，我的21岁还剩下2个小时43分钟，就要22岁了，说真的我还是很害怕长大，
 我好像什么都还没有准备好，大学的/学生时代的最后一个生日，现在在陕服的每一件事情都好像是“最后一次”，心里不舒服但是也无可奈何。2015，2016,2017,2018,2019，
 2020，这几年，真的很美好很美好 ，太多难忘的记忆，好了，到时间了，该回宿舍了，祝我自己：生日快乐，前途似锦，奋斗终身，这里引用基普乔格的12字格言：耐心，忍耐，勤勉，希望，信仰，自律。
 路还很长，干，加油加油加油！！！
 persevere to last.
 2021.11.28
 李红磊
 2021年11月28日21:22:34
 */
public class t20211128 {

    //49.字母异位词分组
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map=new HashMap<>();

        for(String str:strs){
            char[] array=str.toCharArray();
            Arrays.sort(array);
            String key=new String(array);
            List<String> list=map.getOrDefault(key,new ArrayList<String>());
            list.add(str);
            map.put(key,list);

        }
        return new ArrayList<List<String>>(map.values());
    }

    //36.有效的独数
    public boolean isValidSudoku(char[][] board) {
        int[][] row = new int[9][10];
        int[][] col = new int[9][10];
        int[][] box = new int[9][10];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;

                int curNum = board[i][j] - '0';
                if (row[i][curNum] == 1) return false;

                if (col[j][curNum] == 1) return false;

                if (box[j / 3 + (i / 3) * 3][curNum] == 1) return false;

                row[i][curNum] = 1;
                col[j][curNum] = 1;
                box[j / 3 + (i / 3) * 3][curNum] = 1;
            }
        }
        return true;
    }

    //73.矩阵置零
    public void setZeroes(int[][] matrix) {
        HashSet<Integer> row = new HashSet<>();//记录为0的行
        HashSet<Integer> col = new HashSet<>();//记录为0的列

        //记录为0 的行列
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    row.add(i);
                    col.add(j);
                }
            }
        }

        //进行置零操作
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (row.contains(i) || col.contains(j)) matrix[i][j] = 0;
            }
        }

    }

    //740.删除并获得点数
    public int deleteAndEarn(int[] nums) {
     /*
        在偷了三处村庄后这个小偷又来到了第四个村庄进行偷窃。他发现这个村庄得居民变得聪明了，
        将房屋打乱了顺序，并且报警器也变得更加得灵敏，在偷了5块钱后，偷6块钱跟4块钱它都会报警，
        但是由于性能的提升，报警器也有"bug", 那就是偷了5块钱后继续偷5块钱报警器不会触发。
        这小偷还是个程序员呢！

        */
        if(nums.length==0||nums==null)return 0;
        if(nums.length==1)return nums[0];

        int len=nums.length;
        int max=nums[0];
        for(int i=1;i<len;i++)max=Math.max(max,nums[i]);

        int[] all=new int[max+1];
        for(int i=0;i<len;i++)all[nums[i]]++;

        int[] dp=new int[max+1];
        dp[1]=1*all[1];//偷1块钱的情况，就直接是1*1的个数
        dp[2]=Math.max(dp[1],2*all[2]);//偷2块钱的情况，应该是偷0块钱的情况+偷2块钱情况（2*2的个数），跳过偷1的情况，因为说了删除num[i]-1的情况

        for(int i=3;i<=max;i++){
            dp[i]=Math.max(dp[i-1],dp[i-2]+i*all[i]);
        }

        return dp[max];//比如【4,2,3】，最终返回偷4块的情况
    }

    //918.环形子数组的最大和
    public int maxSubarraySumCircular(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];//dp[i]表示以下标为i的元素为结尾的最大子序和
        dp[0] = nums[0];
        int max = dp[0];
        int sum = 0;
        //非环形最大子序和
        for (int i = 1; i < len; i++) {
            sum += nums[i];
            dp[i] = dp[i] + Math.max(0, dp[i - 1]);
            max = Math.max(max, dp[i]);
        }
        //下面为计算环形数组的最大子序和
        //先计算最小子序和，然后用数组总和减去最小子序和就是环形数组的最大子序和
        int min = 0;
        for (int i = 1; i < len; i++) {
            //现在的dp[i]:表示以i结尾的【最小】子序he
            dp[i] = nums[i] + Math.min(0, dp[i - 1]);
            min = Math.min(min, dp[i]);
        }

        int circle = sum - min;
        return Math.max(circle, max);

    }


    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (nums == null || nums.length < 4) return res;
        int len = nums.length;
        Arrays.sort(nums);

        for (int i = 0; i < len - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < len - 2; j++) {
                if (j > 1 && nums[j - 1] == nums[j]) continue;
                int sum = nums[i] + nums[j];

                int l = j + 1, r = len - 1;
                while (l < r) {
                    int tem = nums[l] + nums[r];
                    if (tem + sum == target) {
                        ArrayList<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[l]);
                        list.add(nums[r]);
                        res.add(new ArrayList<>(list));
                        while (l + 1 < r && nums[l + 1] == nums[l]) l++;
                        while (r - 1 > l && nums[r - 1] == nums[r]) r--;
                        l++;
                        r--;
                    } else if (tem + sum > target) {
                        r--;
                    } else {
                        l++;
                    }
                }

            }
        }
        return res;
    }

    public static void main(String[] args) {
        t20211128 t20211128 = new t20211128();



    }


}
